#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	enum presence {zero, one, dont};
	int n, C;          // Число предметов и максимальный вес
	cin >> n >> C;
	vector<int> c(n), w(n);   // Стоимость предметов и их веса
	for (int i = 0; i < n; ++i) {
		cin >> c[i] >> w[i];
	}
	deque<vector<presence>> queue;
	int record = 0;
	vector<presence> cur(n, dont);
	queue.push_back(cur);
	while (!queue.empty()) {
		cur = queue.front();
		queue.pop_front();
		cout << "Набор:" << endl;
		for(int i = 0; i < n; ++i) {
			if (cur[i] == zero) cout << "0 ";
			else if (cur[i] == one) cout << "1 ";
			else cout << "_ ";
		}
		cout << endl;
		
		int cur_record = 0, cur_weight = 0;
		for (int i = 0; i < n; ++i) {
			if (cur[i] == one) {
				cur_record += c[i];
				cur_weight += w[i];
			}
		}
		if (cur_weight > C) {
			cout << "Суммарный вес превзошел ограничения" << endl;
			continue;
		}
		int s = 0;
		while (s < n && C - cur_weight >= 0) {
			if (cur[s] == dont) {
				cur_weight += w[s];
				cur_record += c[s];
			}
			s += 1;
		}
		--s;
		if (C - cur_weight < 0) {
			cur_weight -= w[s];
			cur_record -= c[s];
		} else {
			if (cur_record > record) {
				record = cur_record;
			}
			cout << "Все оставшиеся предметы вошли в набор" << endl;
			continue;
		}
		cout << "Дробная переменная: " << s+1 << endl;
		cout << "Текущий вес: " << cur_weight << endl;
		cout << "Текущий рекорд: " << cur_record << endl;
		double ULR = cur_record + double(c[s])/w[s]*(C-cur_weight);
		if (cur_record > record) {
			record = cur_record;
		}
		cout << "Глобальный рекорд: " << record << endl;
		if (ULR < record) {
			cout << "Дробный рекорд ULR меньше максимального: " << ULR << "<" << record << endl;
			vector<presence> task1 = cur;
			task1[s] = zero;
			queue.push_back(task1);
			continue;
		}
		vector<presence> task1 = cur, task2 = cur;
		task1[s] = zero;
		task2[s] = one;
		queue.push_back(task1);
		queue.push_back(task2);
	}
	cout << record << endl;
	return 0;
}